package top.likeqc.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @see <a href="https://leetcode.cn/problems/maximum-frequency-stack">leetcode题库</a>
 */
public class MaximumFrequencyStack {
    public static void main(String[] args) {
        FreqStack freqStack = new MaximumFrequencyStack().new FreqStack();

        freqStack.push(5);
        freqStack.push(7);
        freqStack.push(5);
        freqStack.push(7);
        freqStack.push(4);
        freqStack.push(5);

        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
    }
    // leetcode submit region begin(Prohibit modification and deletion)
    class FreqStack {

        Map<Integer, List<Integer>> map = new HashMap<>();
        Map<Integer, Integer> cnts = new HashMap<>();
        int max;

        public FreqStack() {}

        public void push(int val) {
            cnts.put(val, cnts.getOrDefault(val, 0) + 1);
            int c = cnts.get(val);
            List<Integer> list = map.getOrDefault(c, new ArrayList<>());
            list.add(val);
            map.put(c, list);
            max = Math.max(max, c);
        }

        public int pop() {
            List<Integer> list = map.get(max);
            Integer ans = list.remove(list.size() - 1);

            if (cnts.get(ans) == 1) {
                cnts.remove(ans);
            } else {
                cnts.put(ans, cnts.get(ans) - 1);
            }

            if (list.size() == 0) {
                max--;
            }

            return ans;
        }
    }

    /**
     * Your FreqStack object will be instantiated and called as such: FreqStack obj = new
     * FreqStack(); obj.push(val); int param_2 = obj.pop();
     */
    // leetcode submit region end(Prohibit modification and deletion)

}
